class Solution
{
public:
    bool isValidSerialization(string preorder)
    {
        if (preorder == "#")
        {
            return true;
        }
        stack<bool> nextIsLeft;
        int i = 0;
        for (char &c : preorder)
        {
            if (c == ',')
            {
                c = ' ';
            }
        }
        stringstream ss(preorder);
        string node;
        bool treeEnd = false;
        while (ss >> node)
        {
            if (treeEnd)
            {
                return false;
            }
            if (node == "#")
            {
                if (nextIsLeft.empty())
                {
                    return false;
                }
                while (!nextIsLeft.empty())
                {
                    if (nextIsLeft.top())
                    {
                        nextIsLeft.top() = false;
                        break;
                    }
                    else
                    {
                        nextIsLeft.pop();
                    }
                }
                if (nextIsLeft.empty())
                {
                    treeEnd = true;
                }
            }
            else
            {
                nextIsLeft.push(true);
            }
        }
        return treeEnd;
    }
};